// Copyright 2019 Glenn McIntosh
// licensed under the GNU General Public Licence version 3
#pragma once
/** @file erasure.h
	erasure codes
	*/
// include files
#include <cstdint>

// clmul optimization on GCC for x86
#ifdef __x86_64__
#pragma GCC target("pclmul")
#include <immintrin.h>
inline uint64_t clmul32(uint32_t x, uint32_t y)
{
	return __builtin_ia32_pclmulqdq128(__v2di{x}, __v2di{y}, 0)[0];
}
#define CLMUL
#endif

// clmul optimization on VC for x86
#ifdef _M_AMD64
#include <immintrin.h>
#pragma intrinsic(_mm_clmulepi64_si128)
inline uint64_t clmul32(uint32_t x, uint32_t y)
{
	__m128i x1, y1;
	x1.m128i_i64[0] = x; y1.m128i_i64[0] = y;
	return _mm_clmulepi64_si128(x1, y1, 0).m128i_i64[0];
}
#define CLMUL
#endif

// clmul optimization on GCC for ARM
// compile with gcc -mfpu=crypto-neon-fp-armv8 -D__ARM_FEATURE_CRYPT
#ifdef __ARM_FEATURE_CRYPT
#include <arm_neon.h>
inline uint64_t clmul32(uint32_t x, uint32_t y)
{
	return vmull_p64(x, y);
}
#define _CLMUL
#endif

namespace math
{
// random bit table for up to 2048 selections
static constexpr uint32_t select_table[] =
{
	0x24fc5611,0xa1c510cb,0xc8985174,0xc00ece22,0x25901c44,0x94f98c0b,0x10745f19,0x37723691,
	0xa2148467,0x1c0bc8ee,0x7d2a66f3,0x2c973036,0x033594ed,0x933e0abb,0xfc21abad,0xade290e8,
	0x4968ab9b,0x919edfd8,0x8b8cd065,0x19fbad35,0xf4bf4edb,0x0b58fbed,0x1d87f5b7,0x56647e69,
	0x5d3e09a2,0x8f34fe99,0x248599e2,0xcd8936ef,0x10804f47,0xa1713f68,0xc696041b,0x8eea7296,
	0x251a7fc5,0x2fc9bc7e,0xb0a92ef1,0x4e716d1a,0x8ed1b31a,0x41a85277,0xde2a25b8,0x435a9aad,
	0x390cab9c,0x544f06c8,0xa38b0dc4,0x1406a10f,0x53829e18,0x1ddb1cf7,0x719e3b0d,0x065c1870,
	0x367970d1,0x0d78517c,0xeba8ee83,0xbd8cd2e4,0x1ef5f45b,0xaa063a06,0x67aaa4cf,0x55aad529,
	0xea121946,0xc6172802,0xaa539c56,0x54d5086d,0x2d333a2c,0x88821773,0x852a61f5,0x3e4e97c9,
};

/** Luby transform erasure coding.
	@param T packet structure
	@param max_packet maximum number of packets
*/
template<typename T, int max_packets>
class LubyTransformTransmit
{
	using Selection = uint32_t;
	static_assert(max_packets <= sizeof(Selection)*8, "maximum packets exceeds selection mask");
	using Word = uint32_t;
	static constexpr int n_select = sizeof(select_table)/sizeof(*select_table);
	static_assert(sizeof(T)%sizeof(Word) == 0, "packet length not a multiple of word size");
	static constexpr int n_words{sizeof(T)/sizeof(Word)};
	struct Packet {Word words[n_words];};
public:
	/** generate a redundant single packet given a buffer a multiple of the packet length
	@param seed unique seed value
	@param n_packets total number of packets in buffer
	@param packet0 output packet
	@param data0 input data buffer
	*/
	void operator()(int seed, int n_packets, T &packet0, const void *data0)
	{
		// cast parameters
		Packet &packet{reinterpret_cast<Packet &>(packet0)};
		const Packet *data{reinterpret_cast<const Packet *>(data0)};

		// select mix subset
		int index = seed%(n_select*32);
		Selection selection = (select_table[index/32]<<index%32) | select_table[(index/32+1)%n_select]>>32-index%32;
		selection &= (1u<<n_packets)-1;

		// mix several packets into message
		for (int bit = 0; bit < n_packets; ++bit)
			if (selection & 1u<<bit)
				for (int i = 0; i < n_words; ++i)
					packet.words[i] ^= data[bit].words[i];
	}
};

/** Luby transform erasure decoding.
	@param T packet structure
	@param max_packet maximum number of packets
*/
template<typename T, int max_packets>
class LubyTransformReceive
{
	using Selection = uint32_t;
	static_assert(max_packets <= sizeof(Selection)*8, "maximum packets exceeds selection mask");
	using Word = uint32_t;
	static constexpr int n_select = sizeof(select_table)/sizeof(*select_table);
	static_assert(sizeof(T)%sizeof(Word) == 0, "packet length not a multiple of word size");
	static constexpr int n_words{sizeof(T)/sizeof(Word)};
	struct Packet {Word words[n_words];};
public:
	/** receive a redundant single packet into a buffer a multiple of the packet length
	@param seed packet seed value
	@param n_packets total number of packets
	@param packet0 received packet
	@param data0 reconstruction buffer
	*/
	bool operator()(int seed, int n_packets, const T &packet0, void *data0)
	{
		// ignore unneeded packets
		if (n == n_packets)
			return false;
		int index = seed%(n_select*32);
		Selection selection = (select_table[index/32]<<index%32) | select_table[(index/32+1)%n_select]>>32-index%32;
		selection &= (1u<<n_packets)-1;

		// cast parameters
		const Packet &packet{reinterpret_cast<const Packet &>(packet0)};
		Packet * const data{reinterpret_cast<Packet *>(data0)};

		// add to table
		data[n] = packet;

		// remove known bits
		for (int i = 0; i < n; ++i)
			if (selection & pivots[i])
			{
				selection ^= selections[i];
				for (int j = 0; j < n_words; ++j)
					data[n].words[j] ^= data[i].words[j];
			}

		// check if useful
		if ((selection & ~pivot_total) == 0)
			return false;

		// select a pivot (preference lowest bit)
		Selection pivot = (selection ^ selection-1)/2 + 1;
		pivot_total ^= pivot;

		// remove from existing packets
		for (int i = 0; i < n; ++i)
			if (selections[i] & pivot)
			{
				selections[i] ^= selection;
				for (int j = 0; j < n_words; ++j)
					data[i].words[j] ^= data[n].words[j];
			}

		// add to table
		selections[n] = selection;
		pivots[n] = pivot;
		++n;
		if (n < n_packets)
			return false;

		// in-place sort, already partially sorted
		for (int i = 0; i < n; ++i)
			for (int j = i; j < n; ++j)
				if (pivots[j] == 1u<<i)
				{
					std::swap(pivots[i], pivots[j]);
					std::swap(data[i], data[j]);
					break;
			}

	return true;
	}

	/** reset the reconstruction */
	void reset()
	{
		n = 0;
	}
private:
	// single packet
	Selection pivot_total{0};
	Selection selections[max_packets], pivots[max_packets];
	int n{0};
};

// Chinese remainder erasure code
// table of irreducible generating polynomials for GF(2^32)
// upper 16 bits empty, implicit bit 32
// for up to 2048 selections
static constexpr uint16_t prime_table[] =
{
	0x008d,0x00af,0x00c5,0x00f5,0x0125,0x012f,0x0137,0x013b,0x0173,0x0175,0x020d,0x0229,0x025b,0x025d,0x0291,0x029d,
	0x02d9,0x0309,0x033f,0x034b,0x034d,0x03b7,0x03e7,0x03ed,0x041f,0x0475,0x04b3,0x04e3,0x04e5,0x051d,0x0577,0x0599,
	0x059f,0x05db,0x0627,0x0633,0x0693,0x069f,0x06a5,0x06cf,0x06e1,0x06eb,0x0725,0x0731,0x0743,0x0751,0x0779,0x077f,
	0x0783,0x07ad,0x07bf,0x07c1,0x07d3,0x07fb,0x0813,0x0825,0x0829,0x082f,0x0867,0x08cb,0x08d5,0x08f1,0x08f7,0x0905,
	0x093f,0x0955,0x0971,0x098b,0x09a9,0x09e7,0x0a11,0x0a17,0x0a4d,0x0a7d,0x0a87,0x0a99,0x0aa5,0x0abd,0x0b45,0x0b6d,
	0x0b73,0x0b83,0x0bcb,0x0bcd,0x0bd9,0x0be3,0x0c1b,0x0c1d,0x0c53,0x0c71,0x0cc5,0x0cdb,0x0ced,0x0cf5,0x0d5d,0x0d61,
	0x0d79,0x0d97,0x0dab,0x0dad,0x0db9,0x0df1,0x0e0b,0x0e25,0x0e4f,0x0e79,0x0e91,0x0ecd,0x0efd,0x0f1d,0x0f33,0x0f35,
	0x0f39,0x0f6f,0x0f81,0x0f87,0x0fa9,0x0fb1,0x100d,0x107f,0x10a1,0x10b9,0x10c7,0x111b,0x116f,0x11bd,0x11c3,0x11dd,
	0x1241,0x1247,0x1263,0x1269,0x1277,0x127b,0x1287,0x12b1,0x12bd,0x12c5,0x12cf,0x12eb,0x136d,0x137f,0x13ab,0x13d3,
	0x144b,0x144d,0x14a9,0x14d7,0x1523,0x1525,0x1589,0x159b,0x15e5,0x15f7,0x1619,0x1645,0x1651,0x1657,0x165d,0x166b,
	0x16d3,0x16e3,0x16f7,0x1709,0x1747,0x1753,0x1755,0x1759,0x177d,0x178d,0x1799,0x17af,0x1869,0x187d,0x1887,0x1893,
	0x18bd,0x18ed,0x18ff,0x1945,0x1949,0x196b,0x19b3,0x19d9,0x19df,0x1a19,0x1a1f,0x1a45,0x1a51,0x1a6d,0x1a9b,0x1a9d,
	0x1b41,0x1b71,0x1b8d,0x1baf,0x1bbb,0x1bd7,0x1c49,0x1c6b,0x1ca1,0x1ccd,0x1cd9,0x1ce9,0x1d03,0x1d05,0x1d4d,0x1d59,
	0x1d71,0x1df9,0x1dff,0x1e63,0x1e77,0x1e8d,0x1e9f,0x1ec9,0x1ee7,0x1ef3,0x1f45,0x1f4f,0x1f75,0x1fab,0x1fad,0x1fc1,
	0x2019,0x201f,0x204f,0x206b,0x208f,0x20a1,0x20df,0x20e3,0x20e9,0x20f1,0x211d,0x212b,0x2165,0x217d,0x2193,0x21d7,
	0x21db,0x21f5,0x2217,0x224b,0x224d,0x226f,0x2295,0x22a5,0x22bb,0x22c9,0x22ed,0x2325,0x2337,0x2389,0x239b,0x23ad,
	0x23cb,0x23d9,0x23df,0x23e5,0x23e9,0x23f7,0x243f,0x2441,0x2463,0x24a9,0x24d7,0x24dd,0x24f3,0x250d,0x2545,0x255b,
	0x25ad,0x25c7,0x25d3,0x25d5,0x2629,0x266b,0x26ab,0x26cd,0x26df,0x26e3,0x2709,0x2711,0x272d,0x273f,0x2781,0x278b,
	0x27a3,0x27a5,0x27c3,0x27dd,0x27ff,0x281d,0x282b,0x2835,0x2847,0x2855,0x286f,0x2893,0x28b7,0x28bd,0x290b,0x290d,
	0x2923,0x292f,0x29b9,0x29c7,0x29d3,0x29f1,0x2a19,0x2a31,0x2a5b,0x2a5d,0x2a6b,0x2ac1,0x2ae5,0x2af7,0x2b27,0x2b33,
	0x2b47,0x2b55,0x2b63,0x2b7d,0x2b93,0x2ba9,0x2c1f,0x2c29,0x2c3b,0x2c3d,0x2c49,0x2c5b,0x2c83,0x2c9d,0x2ca7,0x2ce3,
	0x2cf1,0x2d09,0x2d2d,0x2d33,0x2d4d,0x2d55,0x2daf,0x2db1,0x2de1,0x2e05,0x2e11,0x2e1b,0x2e35,0x2e53,0x2e59,0x2e65,
	0x2e77,0x2e93,0x2ec3,0x2f15,0x2f37,0x2f49,0x2f61,0x2f79,0x2f8f,0x2fb3,0x2fc7,0x2fcb,0x2fcd,0x3027,0x305f,0x3069,
	0x306f,0x3095,0x30a3,0x30db,0x30e1,0x30f9,0x3107,0x3115,0x3183,0x3185,0x3197,0x31a7,0x31ad,0x31bf,0x31c1,0x31d3,
	0x31f7,0x320d,0x3229,0x324f,0x3251,0x3285,0x328f,0x32bf,0x32df,0x332b,0x332d,0x3359,0x336f,0x3381,0x33a5,0x33a9,
	0x33bb,0x33c5,0x33ff,0x340d,0x341f,0x3425,0x343b,0x3485,0x349d,0x34b5,0x34c7,0x34cb,0x34fb,0x34fd,0x3509,0x355f,
	0x3587,0x3595,0x35af,0x35f5,0x361d,0x3653,0x3663,0x3687,0x368b,0x36bd,0x36f5,0x373d,0x3767,0x377f,0x3789,0x378f,
	0x379b,0x37f1,0x3801,0x3819,0x3837,0x3867,0x3879,0x38a1,0x38e5,0x38fd,0x3905,0x3911,0x3917,0x3921,0x3963,0x3971,
	0x39a3,0x39b1,0x39c5,0x39dd,0x39f3,0x3a1d,0x3a27,0x3a2b,0x3a3f,0x3a4b,0x3a59,0x3a71,0x3a7d,0x3a93,0x3ad7,0x3b1f,
	0x3b2f,0x3b43,0x3b5d,0x3b61,0x3b97,0x3b9b,0x3b9d,0x3bcd,0x3be5,0x3c03,0x3c1b,0x3c27,0x3c53,0x3c6f,0x3c7d,0x3cd1,
	0x3ce7,0x3ceb,0x3d07,0x3d0d,0x3d31,0x3d37,0x3d85,0x3d91,0x3db5,0x3def,0x3e0b,0x3e1f,0x3e43,0x3e5b,0x3e6d,0x3e7f,
	0x3ed3,0x3efd,0x3f1d,0x3f21,0x3f55,0x3f71,0x3f77,0x3f95,0x3fa3,0x3fb1,0x4029,0x4043,0x4061,0x40a7,0x40ab,0x40c7,
	0x40cb,0x40e3,0x411d,0x4121,0x4147,0x414d,0x4153,0x415f,0x4163,0x418d,0x41bd,0x41e1,0x4217,0x4241,0x425f,0x426f,
	0x427b,0x4287,0x4295,0x42af,0x42b1,0x42bd,0x42c9,0x4307,0x431f,0x435b,0x436b,0x436d,0x4373,0x4385,0x4409,0x4427,
	0x4459,0x4463,0x4465,0x446f,0x4477,0x447d,0x44db,0x450b,0x453b,0x4567,0x45a1,0x45c7,0x45cd,0x45d3,0x45f7,0x45fb,
	0x4619,0x4625,0x469b,0x46a1,0x46b5,0x46e9,0x46f7,0x471d,0x4735,0x474d,0x4755,0x4769,0x4781,0x4787,0x47a3,0x47c9,
	0x47ff,0x4833,0x4839,0x4887,0x4899,0x48c3,0x48e7,0x48f5,0x4929,0x4951,0x496d,0x4983,0x4991,0x49d5,0x49e3,0x4a3b,
	0x4a49,0x4a85,0x4aa1,0x4ad9,0x4ae9,0x4aef,0x4b59,0x4b77,0x4b93,0x4b99,0x4bbd,0x4bc9,0x4beb,0x4c07,0x4c23,0x4c45,
	0x4c89,0x4ce9,0x4d03,0x4d09,0x4d4b,0x4d6f,0x4d77,0x4d7d,0x4e0f,0x4e2b,0x4e35,0x4e93,0x4ea5,0x4ee1,0x4f5b,0x4f6b,
	0x4fb3,0x4fcd,0x4fd9,0x4fef,0x501b,0x5021,0x502d,0x5033,0x5035,0x503f,0x505f,0x5065,0x50e7,0x5131,0x515d,0x517f,
	0x519d,0x51d5,0x51df,0x51e9,0x51f1,0x51fd,0x520d,0x5213,0x523b,0x5249,0x5275,0x529d,0x52ab,0x52ad,0x52d3,0x52f7,
	0x534d,0x5365,0x538b,0x539f,0x53b1,0x53c5,0x53dd,0x5407,0x540b,0x5413,0x5419,0x5431,0x544f,0x5467,0x5483,0x54a1,
	0x54cd,0x5503,0x5533,0x5569,0x5595,0x559f,0x55cf,0x55f3,0x55f9,0x5603,0x561b,0x562d,0x5639,0x5641,0x5681,0x568b,
	0x5693,0x56af,0x56bd,0x56f3,0x571f,0x5723,0x573b,0x573d,0x574f,0x5751,0x57ad,0x5813,0x5829,0x588f,0x58b5,0x58b9,
	0x58cd,0x58fd,0x5903,0x5977,0x5995,0x59a3,0x59c9,0x59cf,0x59ed,0x5a77,0x5a7b,0x5aa3,0x5abb,0x5ac5,0x5ad7,0x5af3,
	0x5b1f,0x5b37,0x5b67,0x5ba7,0x5bb5,0x5bc1,0x5be5,0x5c55,0x5c63,0x5c7b,0x5c95,0x5cb1,0x5cc5,0x5d15,0x5d37,0x5d83,
	0x5dcd,0x5de9,0x5dfd,0x5e07,0x5e23,0x5e2f,0x5e31,0x5e51,0x5e5d,0x5f0f,0x5f59,0x5f6f,0x5faf,0x5fc9,0x602b,0x6063,
	0x60a5,0x60a9,0x60c3,0x60c9,0x60d1,0x60d7,0x60e7,0x60f5,0x610d,0x6143,0x6151,0x6157,0x6179,0x61b3,0x61e9,0x61fb,
	0x6225,0x62b5,0x62bf,0x6317,0x631d,0x6321,0x6355,0x635f,0x6371,0x6395,0x63a3,0x63bb,0x63cf,0x63d7,0x63e1,0x6413,
	0x6425,0x6429,0x6457,0x6473,0x647f,0x648f,0x64ab,0x64b5,0x64c7,0x64d9,0x64fd,0x6553,0x65b1,0x65bd,0x6603,0x6659,
	0x66a5,0x66af,0x66c3,0x66cf,0x66db,0x66dd,0x66eb,0x66f9,0x671f,0x6723,0x6725,0x6731,0x676d,0x67b9,0x67e3,0x67f1,
	0x680b,0x6861,0x689b,0x68ad,0x68c1,0x68df,0x68e9,0x690f,0x6965,0x698b,0x69af,0x69c3,0x69db,0x69ff,0x6a21,0x6a2b,
	0x6a55,0x6a59,0x6ae1,0x6af3,0x6b07,0x6b6d,0x6ba1,0x6ba7,0x6bb3,0x6bb5,0x6bef,0x6bfb,0x6c05,0x6c17,0x6c69,0x6c7b,
	0x6ce1,0x6cf5,0x6d19,0x6d73,0x6d89,0x6d9d,0x6db9,0x6dbf,0x6dd3,0x6dd5,0x6e1f,0x6e6d,0x6e83,0x6e8f,0x6ea7,0x6eab,
	0x6ecd,0x6f03,0x6f77,0x6f93,0x6f99,0x6fa5,0x6faf,0x6fcf,0x702f,0x7075,0x709b,0x70cd,0x70d9,0x7105,0x711d,0x7133,
	0x719f,0x71c5,0x71d7,0x720f,0x7265,0x7277,0x728d,0x72e7,0x7307,0x7319,0x7351,0x7367,0x738f,0x73c1,0x73d3,0x7405,
	0x7417,0x747d,0x7481,0x74eb,0x7515,0x7531,0x756b,0x7573,0x7583,0x75cd,0x75df,0x7657,0x766d,0x7673,0x7691,0x76cb,
	0x76d9,0x7705,0x774d,0x7795,0x77c3,0x77d7,0x780f,0x7817,0x786f,0x7871,0x78c9,0x78dd,0x7923,0x7949,0x7991,0x7997,
	0x7a19,0x7a1f,0x7a4f,0x7aab,0x7ab9,0x7ae5,0x7b27,0x7b63,0x7b65,0x7ba9,0x7bbb,0x7be7,0x7c07,0x7c3b,0x7c61,0x7c6b,
	0x7c9d,0x7cdf,0x7d17,0x7d1b,0x7d53,0x7d7b,0x7d99,0x7dcf,0x7e09,0x7e21,0x7e33,0x7e4d,0x7e5f,0x7e71,0x7f0b,0x7f19,
	0x7f61,0x7f73,0x7f9b,0x7f9d,0x7fc1,0x7fd5,0x8045,0x805b,0x8083,0x80a1,0x80b5,0x80c7,0x8103,0x8159,0x8169,0x817b,
	0x817d,0x81b1,0x81e7,0x8217,0x8233,0x8255,0x825f,0x827b,0x8299,0x829f,0x82d7,0x82dd,0x82e1,0x82eb,0x8349,0x8375,
	0x83bf,0x83c1,0x83c7,0x8403,0x8447,0x844d,0x8471,0x84a9,0x84db,0x84ed,0x84ff,0x850b,0x852f,0x85bf,0x85d9,0x85f7,
	0x8607,0x8619,0x8631,0x8667,0x8675,0x86d3,0x86e5,0x8727,0x8753,0x877d,0x8781,0x879f,0x87a5,0x87b7,0x87bb,0x87bd,
	0x87d1,0x87f3,0x8817,0x8835,0x884b,0x8869,0x88a5,0x88ed,0x8915,0x8929,0x8961,0x896d,0x89a1,0x89d5,0x8a2f,0x8a45,
	0x8a49,0x8a51,0x8a67,0x8a75,0x8acb,0x8ad9,0x8ae3,0x8b05,0x8b1b,0x8b1d,0x8b39,0x8b71,0x8b87,0x8b8d,0x8bd7,0x8c23,
	0x8c37,0x8c3d,0x8c49,0x8c67,0x8cd9,0x8d0f,0x8d1d,0x8d35,0x8d47,0x8d4b,0x8d55,0x8d7b,0x8d87,0x8dc9,0x8ddb,0x8dff,
	0x8e53,0x8e55,0x8e65,0x8e77,0x8e7d,0x8ea5,0x8eaf,0x8eb7,0x8ec3,0x8ec5,0x8edb,0x8f6b,0x8f75,0x8f79,0x8f9d,0x8fab,
	0x8fcd,0x900f,0x902b,0x9065,0x9069,0x9071,0x908b,0x908d,0x90bd,0x90dd,0x90e7,0x910d,0x911f,0x912f,0x9145,0x9149,
	0x91ad,0x91b9,0x91bf,0x924f,0x925b,0x926b,0x9285,0x928f,0x9297,0x92a7,0x92b5,0x9335,0x9341,0x935f,0x9387,0x93c9,
	0x9473,0x9479,0x94c1,0x94c7,0x94d5,0x94e9,0x94f7,0x951d,0x954b,0x9553,0x9563,0x956f,0x95c3,0x95e7,0x95f5,0x9611,
	0x9617,0x9647,0x9663,0x9687,0x96bb,0x970b,0x9723,0x975b,0x976b,0x979b,0x97a1,0x97b3,0x9843,0x9845,0x9857,0x9861,
	0x986d,0x98bf,0x98d3,0x98d5,0x98fd,0x9917,0x9921,0x9933,0x9947,0x999f,0x99cf,0x99d1,0x99dd,0x99e1,0x99eb,0x99f5,
	0x9a03,0x9a3f,0x9a4b,0x9a69,0x9a81,0x9a95,0x9ab7,0x9add,0x9ae7,0x9b83,0x9b9d,0x9bd5,0x9bf1,0x9c2d,0x9c35,0x9c41,
	0x9c47,0x9c59,0x9c71,0x9c8d,0x9ca5,0x9cb7,0x9cc5,0x9cff,0x9d89,0x9d8f,0x9d9b,0x9da1,0x9dad,0x9dd5,0x9de9,0x9e19,
	0x9e37,0x9e3d,0x9e5b,0x9e5d,0x9ead,0x9f03,0x9f2b,0x9f33,0x9f5f,0x9f93,0x9f9f,0x9fe1,0x9ff3,0xa00f,0xa027,0xa047,
	0xa04d,0xa08d,0xa0db,0xa0eb,0xa107,0xa13d,0xa149,0xa17f,0xa183,0xa191,0xa1a7,0xa1b5,0xa1d3,0xa1e9,0xa23b,0xa257,
	0xa297,0xa29b,0xa2a1,0xa2ab,0xa2df,0xa2e9,0xa2f7,0xa303,0xa335,0xa363,0xa371,0xa381,0xa3a5,0xa3c5,0xa3f3,0xa3ff,
	0xa445,0xa44f,0xa45b,0xa473,0xa485,0xa4a7,0xa4b5,0xa4cb,0xa4fb,0xa521,0xa54b,0xa587,0xa609,0xa61d,0xa62b,0xa633,
	0xa65f,0xa69f,0xa6a9,0xa6af,0xa72f,0xa737,0xa761,0xa7a7,0xa7b9,0xa7d5,0xa7e3,0xa7ef,0xa82f,0xa843,0xa851,0xa85b,
	0xa867,0xa8a7,0xa8ad,0xa90f,0xa91d,0xa921,0xa955,0xa995,0xa9b1,0xa9b7,0xa9c5,0xa9dd,0xa9f9,0xaa09,0xaa27,0xaa2b,
	0xaa3f,0xaa71,0xaab7,0xaad7,0xaae1,0xaaff,0xab07,0xab0b,0xab0d,0xab31,0xab3d,0xab43,0xab97,0xabbf,0xabc1,0xabe5,
	0xac59,0xac65,0xac81,0xac87,0xacaf,0xacc3,0xad23,0xad49,0xad4f,0xad57,0xad73,0xad7f,0xad85,0xadcb,0xae19,0xae25,
	0xae29,0xae37,0xae73,0xaeab,0xaeb9,0xaecb,0xaeef,0xaef7,0xaefd,0xaf17,0xaf1b,0xaf2b,0xaf3f,0xaf5f,0xaf65,0xaf69,
	0xaf7b,0xafa9,0xafbd,0xafdd,0xb02f,0xb03d,0xb09d,0xb0c1,0xb0cd,0xb0f7,0xb0fb,0xb11d,0xb12d,0xb159,0xb165,0xb16f,
	0xb171,0xb19f,0xb1bd,0xb1d1,0xb211,0xb217,0xb263,0xb26f,0xb28d,0xb293,0xb2a5,0xb301,0xb319,0xb323,0xb343,0xb35b,
	0xb391,0xb3b5,0xb3cd,0xb3fd,0xb41b,0xb447,0xb453,0xb463,0xb4c5,0xb4f5,0xb4f9,0xb53b,0xb545,0xb561,0xb57f,0xb5a7,
	0xb5ab,0xb5b5,0xb5b9,0xb5cb,0xb5d3,0xb5f1,0xb61f,0xb623,0xb65b,0xb685,0xb6a1,0xb6fb,0xb721,0xb727,0xb741,0xb759,
	0xb76f,0xb77d,0xb793,0xb7af,0xb7b7,0xb7bd,0xb7ff,0xb803,0xb811,0xb855,0xb865,0xb8a9,0xb8e1,0xb8ff,0xb907,0xb90d,
	0xb973,0xb98f,0xb9ad,0xb9bf,0xba2f,0xba31,0xba51,0xba79,0xba7f,0xba91,0xbaad,0xbac1,0xbadf,0xbb03,0xbb1d,0xbb4b,
	0xbb4d,0xbb5f,0xbb71,0xbb93,0xbbb1,0xbbe1,0xbbed,0xbc9d,0xbccb,0xbcf7,0xbd1b,0xbd21,0xbd33,0xbd41,0xbd4d,0xbd71,
	0xbd9f,0xbda9,0xbdc3,0xbdcf,0xbdd7,0xbe2d,0xbe35,0xbe41,0xbe59,0xbe69,0xbe6f,0xbe7b,0xbe8b,0xbe93,0xbe99,0xbea5,
	0xbeb1,0xbecf,0xbeeb,0xbf07,0xbf23,0xbf37,0xbf49,0xbf57,0xbf91,0xbf97,0xbfa1,0xbfb3,0xbfe9,0xc01b,0xc041,0xc059,
	0xc07d,0xc0b7,0xc0cf,0xc0eb,0xc0f5,0xc0ff,0xc115,0xc129,0xc15d,0xc16b,0xc197,0xc1c7,0xc1cb,0xc1cd,0xc1e3,0xc1e9,
	0xc219,0xc21f,0xc229,0xc245,0xc26d,0xc273,0xc283,0xc2cb,0xc2d9,0xc2f1,0xc305,0xc309,0xc387,0xc38b,0xc395,0xc3a3,
	0xc3f9,0xc407,0xc413,0xc475,0xc489,0xc4a7,0xc4ad,0xc4bf,0xc4d3,0xc4d9,0xc4ef,0xc4fb,0xc505,0xc517,0xc547,0xc54b,
	0xc555,0xc563,0xc5b1,0xc5db,0xc5e1,0xc5f3,0xc5f9,0xc603,0xc639,0xc63f,0xc66f,0xc68d,0xc6a5,0xc73d,0xc761,0xc785,
	0xc79b,0xc79d,0xc7b3,0xc7b9,0xc7f7,0xc831,0xc891,0xc8fb,0xc903,0xc911,0xc933,0xc94d,0xc96f,0xc981,0xc995,0xc999,
	0xc9bd,0xca09,0xca0f,0xca2d,0xca87,0xcac5,0xcad1,0xcaeb,0xcaf5,0xcb01,0xcb19,0xcb51,0xcb5b,0xcb75,0xcbad,0xcbef,
	0xcbf1,0xcc39,0xcc59,0xcc7b,0xcc93,0xcc9f,0xccc5,0xccf9,0xcd07,0xcd15,0xcd23,0xcd31,0xcd5b,0xcd75,0xcd97,0xcdb3,
	0xcdcb,0xcde5,0xce07,0xce31,0xce45,0xce4f,0xce61,0xceab,0xceb9,0xcecd,0xcee9,0xcf03,0xcf0f,0xcf27,0xcf2d,0xcf41,
	0xcf59,0xcf7d,0xcf8d,0xcfe1,0xd00d,0xd03d,0xd043,0xd049,0xd089,0xd08f,0xd09d,0xd0a7,0xd0cb,0xd0d3,0xd117,0xd13f,
	0xd163,0xd17b,0xd195,0xd1a9,0xd1af,0xd1eb,0xd1f3,0xd211,0xd24b,0xd253,0xd293,0xd2b1,0xd2c3,0xd2d1,0xd307,0xd315,
	0xd325,0xd3a7,0xd3d5,0xd3d9,0xd409,0xd41d,0xd427,0xd435,0xd439,0xd441,0xd477,0xd481,0xd49f,0xd4af,0xd4bb,0xd4bd,
	0xd4ed,0xd4f3,0xd50b,0xd519,0xd53b,0xd53d,0xd543,0xd58f,0xd597,0xd5d3,0xd5e5,0xd5f1,0xd615,0xd631,0xd66b,0xd675,
	0xd67f,0xd683,0xd689,0xd6a1,0xd6cb,0xd6e5,0xd6f7,0xd733,0xd759,0xd771,0xd855,0xd85f,0xd877,0xd88b,0xd89f,0xd8bd,
	0xd8c5,0xd901,0xd90b,0xd913,0xd919,0xd951,0xd961,0xd97f,0xd989,0xd9a7,0xd9bf,0xd9f7,0xda01,0xda0d,0xda1f,0xda37,
	0xda5b,0xda8f,0xda91,0xdaa7,0xdab5,0xdae9,0xdaef,0xdb17,0xdb21,0xdb5f,0xdb93,0xdbc3,0xdbeb,0xdc0b,0xdc3b,0xdc67,
	0xdc97,0xdcab,0xdcb3,0xdcbf,0xdcc7,0xdce5,0xdd39,0xdd53,0xdd59,0xdd77,0xdd7d,0xdde7,0xddf5,0xde17,0xde2b,0xde33,
	0xdeb1,0xdebb,0xdec9,0xdecf,0xdf07,0xdf31,0xdf5d,0xdf7f,0xdf89,0xdf97,0xdfc1,0xdfdf,0xdfef,0xe007,0xe043,0xe051,
	0xe05b,0xe06d,0xe075,0xe079,0xe0b3,0xe0c1,0xe0d3,0xe0f7,0xe135,0xe159,0xe15f,0xe163,0xe187,0xe18d,0xe1a3,0xe1b1,
	0xe1b7,0xe209,0xe21d,0xe239,0xe253,0xe27d,0xe28b,0xe2bb,0xe2c9,0xe2e1,0xe307,0xe31f,0xe35d,0xe36b,0xe411,0xe42d,
	0xe43f,0xe44b,0xe465,0xe493,0xe4af,0xe4b1,0xe4b7,0xe4c3,0xe4dd,0xe507,0xe513,0xe515,0xe523,0xe529,0xe55b,0xe573,
	0xe601,0xe60b,0xe66d,0xe67f,0xe6ab,0xe6c7,0xe6d9,0xe6e5,0xe721,0xe7a9,0xe7af,0xe7c3,0xe7cf,0xe7f9,0xe811,0xe839,
	0xe88d,0xe8bb,0xe8f9,0xe8ff,0xe90b,0xe925,0xe937,0xe983,0xe9a1,0xe9d9,0xe9e5,0xea43,0xea67,0xea75,0xea85,0xea8f,
	0xeaad,0xeab3,0xeaf1,0xeb41,0xeb47,0xeb55,0xeb65,0xeb7d,0xeb93,0xeb9f,0xec15,0xec49,0xeca1,0xecb9,0xeccb,0xed05,
	0xed17,0xed1b,0xed27,0xed35,0xed87,0xeda5,0xedb1,0xee1b,0xee1d,0xee39,0xee5f,0xee71,0xee87,0xee8d,0xee99,0xeed1,
	0xeee7,0xef29,0xef3b,0xef3d,0xefb5,0xefbf,0xefd5,0xefe5,0xeff7,0xf039,0xf063,0xf099,0xf0a9,0xf0d7,0xf0e7,0xf13d,
	0xf14f,0xf197,0xf19d,0xf1cd,0xf1e5,0xf207,0xf20b,0xf24f,0xf285,0xf2df,0xf2e9,0xf2ef,0xf2f7,0xf347,0xf355,0xf369,
	0xf381,0xf393,0xf3a3,0xf3a9,0xf3b7,0xf3c9,0xf40d,0xf443,0xf451,0xf475,0xf48f,0xf4a7,0xf4ad,0xf4b5,0xf4d3,0xf4ef,
	0xf4fd,0xf541,0xf595,0xf5af,0xf5c5,0xf5d1,0xf5dd,0xf62d,0xf633,0xf63f,0xf641,0xf659,0xf65f,0xf687,0xf68b,0xf695,
	0xf6b1,0xf6b7,0xf713,0xf737,0xf757,0xf785,0xf78f,0xf79d,0xf807,0xf81f,0xf823,0xf829,0xf82f,0xf831,0xf843,0xf873,
	0xf885,0xf8bf,0xf8cd,0xf941,0xf965,0xf98b,0xf999,0xf9db,0xf9e7,0xf9ff,0xfa39,0xfa4d,0xfa69,0xfa7b,0xfa8d,0xfaa5,
	0xfaa9,0xfaf9,0xfb2f,0xfb4f,0xfb75,0xfbc1,0xfbf7,0xfc1b,0xfc1d,0xfc41,0xfc4d,0xfc65,0xfc69,0xfc87,0xfcb1,0xfcbd,
	0xfcdd,0xfceb,0xfd29,0xfd51,0xfd57,0xfd8f,0xfda7,0xfe23,0xfe61,0xfe83,0xfe85,0xfe97,0xfeb5,0xfefd,0xff03,0xff27,
	0xff33,0xff53,0xffaf,0xffb7,
};

/** Chinese remainder erasure coding.
	@param T packet structure
	@param max_packet maximum number of packets
*/
template<typename T, int max_packets>
class RemainderErasureTransmit
{
	// single word of multiprecision type
	using Word = uint32_t;
	using Word2 = uint64_t;
	static constexpr int bits{sizeof(Word)*8};
	static_assert(sizeof(T)%sizeof(Word) == 0, "packet length not a multiple of word size");
	static constexpr int n_words{sizeof(T)/sizeof(Word)};
	struct Packet {Word words[n_words];};
	static constexpr int n_primes = sizeof(prime_table)/sizeof(*prime_table);
public:
	/** generate a redundant single packet given a buffer a multiple of the packet length
	@param seed unique seed value
	@param n_packets total number of packets in buffer
	@param packet0 output packet
	@param data0 input data buffer
	*/
	void operator()(int seed, int n_packets, T &packet0, const void *data0)
	{
		// cast parameters
		Packet &packet{reinterpret_cast<Packet &>(packet0)};
		const Packet *data{reinterpret_cast<const Packet *>(data0)};

		// mix all packets into packet
		int selection = seed%n_primes;
		Word p = prime_table[selection];
		for (int j = 0; j < n_words; ++j)
		{
			Word r{data[n_packets-1].words[j]};
			for (int i = n_packets-2; i >= 0; --i)
				r = clmod(r, p) ^ data[i].words[j];
			packet.words[j] = r;
		}
	}
private:
	// GF(2^32) r|0 modulo 1|p
	static Word clmod(Word r, Word p)
	{
#		ifdef CLMUL
		// this optimization assumes that the upper half of p is 0
		Word2 r2 = clmul32(r, p);
		r = r2 ^ clmul32(r2>>bits, p);
#		else
		for (int b = 0; b < bits; ++b)
			r = r<<1 ^ -(r>>bits-1&1) & p;
#		endif
		return r;
	}
};

/** Chinese remainder erasure decoding.
	@param T packet structure
	@param max_packet maximum number of packets
*/
template<typename T, int max_packets>
class RemainderErasureReceive
{
	// single word of multiprecision type
	using Word = uint32_t;
	using Word2 = uint64_t;
	static constexpr int bits{sizeof(Word)*8};
	static_assert(sizeof(T)%sizeof(Word) == 0, "packet length not a multiple of word size");
	static constexpr int n_words{sizeof(T)/sizeof(Word)};
	struct Packet {Word words[n_words];};
	static constexpr int n_primes = sizeof(prime_table)/sizeof(*prime_table);
public:
	/** receive a redundant single packet into a buffer a multiple of the packet length
	@param seed packet seed value
	@param n_packets total number of packets
	@param packet0 received packet
	@param data0 reconstruction buffer
	*/
	bool operator()(int seed, int n_packets, const T &packet0, void *data0)
	{
		// ignore unneeded packets
		if (n == n_packets)
			return false;

		// cast parameters
		const Packet &packet{reinterpret_cast<const Packet &>(packet0)};
		Packet * const data{reinterpret_cast<Packet *>(data0)};

		// check if in table
		int selection = seed%n_primes;
		Word prime = prime_table[selection];
		for (int i = 0; i < n; ++i)
			if (prime == primes[i])
				return false;

		// add to table until full
		primes[n] = prime;
		data[n] = packet;
		if (++n < n_packets)
			return false;

		// calculate factors
		uintn f_i[n_packets] = {{n_packets, {1}}};
		int bit_high{1};
		while (bit_high < n_packets)
			bit_high <<= 1;
		for (int bit = bit_high/2; bit; bit /= 2)
		{
			for (int i = 0; i+bit < n_packets; i += bit*2)
			{
				f_i[i+bit] = f_i[i];
				for (int j = 0; j < bit*2 && i+j < n_packets; ++j)
					f_i[(i+bit)^(j&~(bit-1))] *= primes[i+j];
			}
		}

		// calculate inverses
		Word t_i[n_packets];
		for (int i = 0; i < n_packets; ++i)
		{
			Word f = f_i[i] % primes[i];
			Word t = 1;
			for (Word b = 1u<<bits-1; b > 1; b >>= 1)
			{
				t = mulmod(t, f, primes[i]);
				t = mulmod(t, t, primes[i]);
			}
			t_i[i] = t;
		}

		// reconstruct
		for (int j = 0; j < n_words; ++j)
		{
			uintn r = {n_packets, {0}};
			for (int i = 0; i < n_packets; ++i)
				r.accumulate(f_i[i], mulmod(data[i].words[j], t_i[i], primes[i]));
			for (int i = 0; i < n_packets; ++i)
				data[i].words[j] = r.words[i];
		}
		return true;
	}

	/** reset the reconstruction */
	void reset()
	{
		n = 0;
	}
private:
	// GF(2^32) multiply
	static Word2 clmul(Word x, Word y)
	{
#		ifdef CLMUL
		return clmul32(x, y);
#		else
		Word2 r{0}, y2{y};
		for (int b = 0; b <bits; ++b)
			r = r<<1 ^ -((y2<<=1)>>bits&1) & x;
		return r;
#		endif
	}

	// GF(2^32) r|0 modulo 1|p
	static Word clmod(Word r, Word p)
	{
#		ifdef CLMUL
		// this optimization assumes that the upper half of p is 0
		Word2 r2 = clmul32(r, p);
		r = r2 ^ clmul32(r2>>bits, p);
#		else
		for (int b = 0; b < bits; ++b)
			r = r<<1 ^ -(r>>bits-1&1) & p;
#		endif
		return r;
	}

	// polynomial multiply modulo 1|p
	Word mulmod(Word x, Word y, Word p)
	{
#		ifdef CLMUL
		Word2 r2 = clmul(x, y);
		Word r = clmod(r2>>bits, p) ^ r2;
#		else
		Word r = 0;
		Word2 y2{y};
		for (int b = 0; b < bits; ++b)
			r = r<<1 ^ -((y2<<=1)>>bits&1) & x ^ -(r>>bits-1&1) & p;
#		endif
		return r;
	}

	// multiword GF(2^32) accumulator
	struct uintn
	{
		int n_packets;
		Word words[max_packets];

		// modulo 1|p
		Word operator%(Word p)
		{
			Word r{words[n_packets-1]};
			for (int i = n_packets-2; i >= 0; --i)
				r = clmod(r, p) ^ words[i];
			return r;
		}

		// multiply by 1|p
		uintn &operator*=(Word p)
		{
			Word carry{0};
			for (int i = 0; i < n_packets; ++i)
			{
				Word2 r = words[i];
				r = r<<bits ^ clmul(words[i], p);
				words[i] = carry ^ r;
				carry = r>>bits;
			}
			return *this;
		}

		// multiply and accumulate
		void accumulate(const uintn &f, Word y)
		{
			Word carry{0};
			for (int i = 0; i < n_packets; ++i)
			{
				Word2 r = clmul(f.words[i], y);
				words[i] ^= carry ^ r;
				carry = r>>bits;
			}
		}
	};
private:
	int n{0};
	Word primes[max_packets] {0};
};
}
